// 拓扑排序（解决依赖）
// 编译依赖/穿衣服依赖。用有向图存储
// 也可以判断图中是否有环，遍历个数少于顶点总数则有环

#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <string>
using std::cout;
using std::endl;

// 用vector<>，给每个顶点编号012更方便点
typedef std::map<std::string, std::list<std::string>> Graph;

// 1.Kahn算法。先找出入度为0的顶点，使用并移除这个顶点，然后将这个顶点可达的顶点入度都减一，再循环
void Kahn(Graph& graph) {
  std::map<std::string, int> in;  // 入度
  for (auto& item : graph) {
    in[item.first] = 0;
  }
  for (auto& item : graph) {
    auto& lst = item.second;
    for (auto& l : lst) {
      in[l]++;
    }
  }

  std::queue<std::string> que;  // 入度为0的队列
  for (auto& i : in) {
    if (i.second == 0) {
      que.push(i.first);
    }
  }

  while (!que.empty()) {
    std::string key = que.front();
    cout << key << ' ';
    que.pop();
    std::list<std::string>& lst = graph[key];
    for (auto& l : lst) {
      in[l]--;
      if (in[l] == 0) {
        que.push(l);
      }
    }
  }
  cout << endl;
}

void TestKahn() {
  Graph graph;
  graph["a"] = {"b", "c"};
  graph["b"] = {"d"};
  graph["c"] = {"e"};
  graph["d"] = {};
  graph["e"] = {};
  graph["f"] = {};
  /*
    假设分别向右和向下被依赖，b依赖a，e依赖b，f没有依赖关系
    a->b->d
    c  e
  */
  for (auto& item : graph) {
    cout << item.first << ":" << item.second.size() << ' ';
  }
  cout << endl;

  Kahn(graph);
}

// 2.DFS深度优先遍历算法。

int main() {
  TestKahn();
  return 0;
}